0% completed
Problem Statement
Given an array of integers nums where each element appears three times, and one element appears exactly once, return the single element.
Note: You must solve the problem with linear runtime complexity and use only constant extra space.
Examples
- Example 1:
- Input: nums =
[4, 3, 3, 3] - Expected Output:
4 - Justification:
4is the only number that appears once, while3appears three times.
- Input: nums =
- Example 2:
- Input: nums =
[99, 1, 99, 99, 2, 2, 2] - Expected Output:
1 - Justification:
1appears exactly once whereas99and2each appear three times.
- Input: nums =
- Example 3:
- Input: nums =
[0, 7, 2, 7, 2, 7, -1, 2, -1, -1] - Expected Output:
0 - Justification:
0is the unique number appearing once, while7,2and-1appear three times.
- Input: nums =
Solution
To solve this problem, we'll employ bitwise manipulation techniques, which are both space-efficient and run in linear time. The essence of this approach is to count the number of times each bit appears in all numbers. Since every number, except for one, appears exactly three times, a bit set in the unique number will contribute to the total count in a way that's not divisible by three. By iterating over each bit position and summing the occurrence of bits in that position across all numbers, we can determine which bits belong to the unique number. We'll then reconstruct this number from its bits.
This method is effective because it directly leverages the fixed repetition count and the bitwise nature of integers to sidestep the need for additional memory that would be required for hash table-based approaches.
Step-by-Step Algorithm
-
Initialize a Bit Count Array:
- Create an array
bitCountwith a size equal to the number of bits in an integer (32 bits for standard integers). This array will track the count of 1s in each bit position across all numbers in the input array.
- Create an array
-
Count Bits for Each Number:
- Iterate over each number in the input array.
- For each number, iterate over each bit position from 0 to 31.
- Right shift the number by
ibits and apply a bitwise AND with 1 to isolate the bit at positioni. - Add the result to the
ith position in thebitCountarray to count the occurrences of 1s in this bit position across all numbers.
- Right shift the number by
-
Reconstruct the Single Number:
- Initialize a variable
resultto 0. This variable will store the unique number that appears exactly once. - Iterate over the
bitCountarray from 0 to 31 (for each bit position).- If the count in
bitCount[i]is not divisible by 3, it means this bit is set in the unique number (since all other numbers appear exactly three times). - Set the
ith bit inresultby using a bitwise OR with(1 << i).
- If the count in
- Initialize a variable
-
Return the Unique Number:
- Return the
result, which now contains the unique number reconstructed from its bits.
- Return the
Algorithm Walkthrough
Let's walkthrough the Input: nums = [0, 7, 2, 7, 2, 7, -1, 2, -1, -1]
-
Initialize
bitCountArray:- Before processing:
bitCount= [0, 0, 0, ..., 0] (32 zeroes for 32-bit positions).
- Before processing:
-
Process Each Number and Update
bitCount:-
Process
0:- No bits to update for
0.bitCountremains unchanged.
- No bits to update for
-
First
7encountered:7in binary is000...0111. Update counts for positions 0, 1, and 2.- After processing:
bitCount= [1, 1, 1, 0, 0, ..., 0].
-
First
2encountered:2in binary is000...0010. Update count for position 1.- After processing:
bitCount= [1, 2, 1, 0, 0, ..., 0].
-
Second
7encountered:- Update counts for positions 0, 1, and 2 again.
- After processing:
bitCount= [2, 3, 2, 0, 0, ..., 0].
-
Second
2encountered:- Update count for position 1.
- After processing:
bitCount= [2, 4, 2, 0, 0, ..., 0].
-
Third
7encountered:- Update counts for positions 0, 1, and 2 again.
- After processing:
bitCount= [3, 5, 3, 0, 0, ..., 0].
-
Third
2encountered:- Update count for position 1.
- After processing:
bitCount= [3, 6, 3, 0, 0, ..., 0].
-
First
-1encountered:-1in binary (two's complement) is all 1s. Update all positions.- After processing:
bitCountbecomes incremented by 1 at each position, e.g., [4, 7, 4, 1, 1, ..., 1].
-
Second
-1encountered:- Again, update all positions by 1.
- After processing:
bitCountincrements by 1 at each position again, e.g., [5, 8, 5, 2, 2, ..., 2].
-
Third
-1encountered:- Once more, update all positions by 1.
- After processing:
bitCountincrements by 1 at each position, e.g., [6, 9, 6, 3, 3, ..., 3].
-
-
Reconstruct the Single Number:
- Iterate over
bitCount. Look for positions where the count is not a multiple of 3. - Since every number except
0has modified thebitCount, and since0does not contribute to any bit position, the only way to detect0is by realizing there's no bit position with a count not divisible by 3 that would contribute to constructing a non-zero result. - The absence of such positions confirms the unique number does not contribute to any bit's count, identifying the unique number as
0.
- Iterate over
-
Return the Unique Number:
- The final
resultis calculated to be0, which correctly identifies it as the unique number not conforming to the thrice occurrence pattern in the input array.
- The final
Code
Complexity Analysis
Time Complexity
The time complexity is K is constant, the time complexity simplifies to
Space Complexity
The space complexity is bitCount used to keep track of the count of each bit across all numbers in the input array. Since K is a constant (32 for an integer), the space complexity simplifies to
On this page
Problem Statement
Examples
Solution
Step-by-Step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity
Space Complexity